\documentclass[12pt,a4paper]{report}

%%Pacotes utilizados para a localização do texto em pt-br
\usepackage[portuguese,brazil]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

%%Pacotes relacionados a escrita matemática e algoritmos
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage[ruled,vlined,linesnumbered]{algorithm2e}

%%Pacotes relacionados a formatação do texto
\usepackage{indentfirst}

%%Pacotes relacionados a imagens
\usepackage{graphicx}
\usepackage{graphics}

\usepackage{latexsym}

\usepackage{color}
\definecolor{Red}{rgb}{1.0, 0.0, 0.0}

\widowpenalty=9999
\clubpenalty=9999

\newtheorem{lema}{Lema}[chapter]
\newtheorem{teo}{Teorema}[chapter]

\author{Bruno Caricchio Buss\\Gabriel Guimarães Mendonça\\Marcelo Rocha Machado\\Ulysses Ulysses Cardoso Vilela}
\title{Tópicos Especiais em Otimização: Double Cut and Join}

\pagestyle{plain}

\textwidth 15cm  % A4 tem 21cm - margens de 3,3 e 2,7
\textheight 23cm % A4 tem 29,7cm

\topmargin -5mm % isto pode ser que dependa da impressora   
%\addtolength{\hoffset}{-1cm}

\parskip 0cm
\parindent 7mm

\begin{document}

\include{capa}

\chapter{Introdução}

O problema de arranjo do genoma foi amplamente estudado em Biologia Computacional.
 Em grande parte das soluções, a transformação de uma cadeia cromossomial em outra
 é avaliada tendo como base apenas uma dentre diversas transformações. Entre elas, citamos:
 reversão, transposição, fissão, fusão e “block interchange”.

Em nosso trabalho, examinamos uma nova operação: \emph{Double Cut and Join (DCJ)}.
 Ela permite a utilização de qualquer uma das transformações antes mencionadas para modificar uma cadeia genética.
 De maneira geral, a DCJ consiste em realizar um corte em duas adjacências do genoma e então colar as 4 ``pontas'' que foram criadas.
 É importante notar que esta operação pode causar a criação de uma componente circular.

Implementamos o algoritmo descrito em \cite{Bergeron} e adicionamos suporte ao modelo restrito descrito em \cite{Kovac}.


\section{DCJ}

A operação de \emph{Double Cut and Join}, como o nome indica, consiste em realizar cortes em duas adjacências do nosso genoma, que vamos chamar de $x$ e $y$, assim criando 4 pontas ($x_1$, $x_2$, $y_1$ e $y_2$) que serão unidas novamente de algum modo.

Com isso, temos 3 possíveis cenários:
\begin{enumerate}
    \item $x$ e $y$ são cortes entre 2 genes. Neste caso teremos:
        \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.8]{dcj_caso1}
        \end{figure}

    \item $x$ é um corte entre 2 genes e $y$ é um corte no extremo de um cromossomo (um telômero). Neste caso teremos:
        \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.8]{dcj_caso2}
        \end{figure}

    \item $x$ e $y$ são cortes no extremo de cromossomos (ou seja, telômeros). Neste caso teremos:
        \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.8]{dcj_caso3}
        \end{figure}
\end{enumerate}

 Ainda podemos ter a operação reversa a 3, onde fazemos um corte entre dois genes e transformamos estes dois em telômeros no genoma.

Através destas operações, é possível reproduzir operações que já conhecemos:
\begin{itemize}

    \item Reversão (1 passo):
        \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.8]{dcj_reversao}
        \end{figure}

    \item Translocação (1 passo):
        \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.8]{dcj_transloc}
        \end{figure}

\clearpage

    \item Transposição (2 passos):
        \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.8]{dcj_transp}
        \end{figure}

    \item Block Interchange (2 passos):
        \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.8]{dcj_blocki}
        \end{figure}

    \item Fusão (1 passo):
        \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.8]{dcj_fusao}
        \end{figure}

\clearpage

    \item Fissão (1 passo):
        \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.8]{dcj_fissao}
        \end{figure}
\end{itemize}

\section{O modelo restrito}

Ao realizar livremente as operações descritas acima, é possível que sejam criadas componentes circulares de genes.
Todavia, ainda que haja na natureza exemplos em que uma componente deste tipo foi criada para depois ser reintegrada a uma componente linear, a situação em que existem diversas componentes lineares é pouco comum e esperada.

Devido a isso, foi introduzido um modelo restrito de DCJ, onde o genoma não pode conter mais do que uma componente circular. Isso implica que, caso uma componente deste tipo seja criada, esta deve ser imediatamente desfeita, tornando-se linear ou, se for o caso, sendo integrada a uma componente linear.

\chapter{O Algoritmo}

O algoritmo implementado foi originalmente proposto em \cite{Bergeron} e tem como objetivo transformar um genoma $A$ em um genoma $B$ no menor número de operações $DCJ$ possíveis.

No algoritmo, modelamos todas as adjacências de $A$ e de $B$ em um grafo que iremos denominar \emph{grafo de adjacências} ou apenas \emph{GA}.
 Iremos criar também arestas correspondentes aos extremos dos genes que correspondem a cada adjacência.
 Um exemplo dessa modelagem é visto na figura abaixo.

\begin{center}
Genoma A: $\displaystyle \overleftarrow{1} \overrightarrow{3} | \overrightarrow{4} \overrightarrow{6} | \overleftarrow{5} \overrightarrow{2}$

Genoma B: $\displaystyle \overrightarrow{1} \overrightarrow{2} \overrightarrow{3} | \overrightarrow{4} \overrightarrow{5} \overrightarrow{6}$
\end{center}

\begin{figure}[htb]
    \centering
    \includegraphics[scale=0.6]{dcj_alg_exemplo_ga}
\end{figure}

O algoritmo então irá percorrer cada adjacência correspondente ao genoma $B$ e verificar se esta adjacência está correta em $A$. Caso não esteja, será realizada uma operação de $DCJ$ para criá-la.
 Por fim, o algoritmo irá verificar todos os telômeros de $B$ e, caso algum não exista em $A$, irá realizar um processo de fissão ou linearização (para o caso de componentes circulares).

No modelo restrito, é adicionada uma verificação após cada iteração do algoritmo a fim de detectar se uma componente circular foi criada e, caso tenha sido, linearizar esta componente ou reintegrá-la a uma componente linear.

\begin{algorithm}

Cria o grafo de adjacências\;

\Para{cada adjacência $\{p, q\}$ em $B$}{

	$u$ = adjacência em $A$ que contém $p$\;
	$v$ = adjacência em $A$ que contém $q$\;

	\Se{$u \neq v$}{
		$u = \{p, q\}$\;
		$v = \{(u \backslash \{p\}), (v \backslash \{q\})\}$\;
	}
}

\Para{cada telomero $\{-, p\}$ ou $\{p, -\}$ em $B$}{

	$u$ = adjacência em $A$ que contém $p$\;

	\Se{u for uma adjacência}{
		$u = \{-, p\}$ ou $\{p, -\}$\;
		Crie um novo nó com $\{-, (u \backslash \{p\})\}$\;
	}
}

\caption{Guloso para modelo geral}
\end{algorithm}

\begin{algorithm}

Cria o grafo de adjacências\;

\Para{cada adjacência $\{p, q\}$ em $B$}{

	$u$ = adjacência em $A$ que contém $p$\;
	$v$ = adjacência em $A$ que contém $q$\;

	\Se{$u \neq v$}{
		$u = \{p, q\}$\;
		$v = \{(u \backslash \{p\}), (v \backslash \{q\})\}$\;
	}

	{\color{Red} Verifica se existe componente circular em $A$, caso sim desfaça}\;
}

\Para{cada telomero $\{-, p\}$ ou $\{p, -\}$ em $B$}{

	$u$ = adjacência em $A$ que contém $p$\;

	\Se{u for uma adjacência}{
		$u = \{-, p\}$ ou $\{p, -\}$\;
		Crie um novo nó com $\{-, (u \backslash \{p\})\}$\;
	}
}

\caption{Guloso para modelo restrito}
\end{algorithm}

\section{Corretude}

Afirmamos anteriormente que o algoritmo guloso que foi apresentado na seção anterior resolve o problema de encontrar a menor quantidade de operações de \emph{DCJ}
 para transformar um genoma $A$ em outro genoma $B$, então aqui iremos provar este fato. Todos os resultados aqui enunciados tem suas provas completas em \cite{Bergeron},
 que vamos omitir ou apenas prover um esboço nesta seção.

\begin{lema}
Uma operação de \emph{DCJ} altera o número de componentes, lineares e circulares, em no máximo 1.
\end{lema}

A prova deste resultado é feita através de uma análise dos casos possíveis.

\begin{lema}
Sejam $A$ e $B$ dois genomas com o mesmo conjunto de $N$ genes cada, então:
\[ A = B \Leftrightarrow N = C + \frac{I}{2}  \]
onde $C$ é o número de ciclos e $I$ é o número de caminhos de tamanho ímpares no grafo de adjacências de $A$ e $B$.
\end{lema}

A ida é fácil de ser verificada, pois cada adjacência que está correta nos dois, corresponde a um ciclo de tamanho dois e cada telomero corresponde a um caminho de tamanho um.
A volta é verificada, observando que cada ciclo contem uma adjacência de $A$ e cada caminho ímpar contem um telomero de $A$, então se $N = C + \frac{I}{2}$ então necessariamente
 o grafo corresponderá a um ciclo de tamanho 2 entre duas adjacências correspondentes de $A$ e $B$ e caminhos de tamanho um entre os telômeros de $A$ e $B$.

\begin{lema}
Uma operação de \emph{DCJ} altera o número de ciclos ímpares no grafo de adjacências em -2, 0 ou +2.
\end{lema}

Novamente, a prova é feita através da análise de casos possíveis.

\begin{lema}
Sejam $A$ e $B$ dois genomas com o mesmo conjunto de $N$ genes cada, então:
\[ d_{DCJ}(A, B) \geq N - (C + \frac{I}{2})  \]
onde $C$ é o número de ciclos e $I$ é o número de caminhos de tamanho ímpares no grafo de adjacências de $A$ e $B$.
\end{lema}

A prova é direta, bastando-se observar que nenhuma operação de \emph{DCJ} altera o número de ciclos e de caminhos ímpares ao mesmo tempo e pelos lemas anteriores.

\begin{teo}
Sejam $A$ e $B$ dois genomas com o mesmo conjunto de $N$ genes cada, então:
\[ d_{DCJ}(A, B) = N - (C + \frac{I}{2})  \]
onde $C$ é o número de ciclos e $I$ é o número de caminhos de tamanho ímpares no grafo de adjacências de $A$ e $B$.
\end{teo}

A prova é através da análise que o algoritmo guloso realiza no máximo $N - (C + \frac{I}{2})$ operações, logo o limite inferior se iguala ao limite superior e temos uma igualdade.

\section{Complexidade}

O algoritmo consiste de duas fases. 

Na fase inicial o grafo de adjacência deve ser criado. Sua construção consiste em criar um vértice para cada adjacência e telomero em $A$ e $B$, e então percorrer $A$ em sua totalidade,
 tanto adjacências como telômeros, e verificar onde as cabeças e caudas de cada gene aparecem em $B$ para criar as arestas do grafo.
 Isto pode ser feito em tempo $O(n)$ já que o tempo para o acesso a um gene e suas adjacências é constante utilizando as tabelas auxiliares.

Já na segunda fase, deve-se percorrer os vértices correspondentes as adjacências e telômeros de $B$ no grafo criado e então, para cada adjacência de $B$, se não existir
 a correspondente em $A$, então uma operação de DCJ será feita. Finalmente os telômeros de B são percorridos e se necessário será feito uma fissão em alguma adjacência em $A$.
 Novamente, nós podemos dizer que o tempo de execução é $O(n)$, como temos dois laços, uma para adjacência e um para telômeros, porém sabemos que soma da quantidade é da
 ordem de $n$. Além disso, com as tabelas auxiliares, podemos realizar as operações em tempo constante.

Logo a complexidade total do algoritmo é $O(n + n) = O(n)$.

Ao adicionarmos suporte ao modelo restrito, adicionamos no final de cada iteração do loop que olha as adjacências de $B$ uma verificação se alguma componente circular foi criada e
 caso positivo um procedimento para desfazer o ciclo ou então reintegra-lo em outra componente linear.

Verificar se existe um ciclo, partindo das adjacências modificadas, pode ser feito em $O(n)$, pois o  nosso grafo tem uma quantidade de vértice de ordem $n$.
 Desfazer um ciclo é $O(n)$ também, pois é necessário percorrer o ciclo e encontrar uma adjacênica onde iremos quebra-lo.

Portanto, a complexidade total do algoritmo com a restrição de adjacência é de $O(n^2 + n) = O(n^2)$.

\chapter{Implementação}

	Para implementar o algoritmo deste trabalho, foi desenvolvido um programa em C, capaz de reconhecer entrada de dados, gerar um log informativo e de depuração e criar entradas de dados aleatórias. Foram usadas somente as estruturas de dados nativas da linguagem visto que o algoritmo só utiliza as tabelas indexadas que traduzimos em vetores ou matrizes.

\section{Entrada de Dados}

	Para implementar o algoritmo foi definido um formato para os dados de entrada, que compreende em um arquivo com 3 linhas:
\begin{itemize}
    \item a primeira linha contém um número com o comprimento do genoma;
    \item a segunda linha contém o genoma original;
    \item a terceira linha contém o genoma alvo.
\end{itemize}
	
	Cada gene é representado por um número, e possui um sinal que indica sua orientação. Para indicar as quebras, utilizamos o sinal de pipe '|' nos genomas. Um arquivo de entrada segue o exemplo abaixo:

\begin{center}
\begin{verbatim}
11
+1 -2 -3 +4 +9 -8 +7 | +10 -5 -6 | +11
+1 +2 +3 | +4 +5 +6 | +7 +8 +9 +10 +11
\end{verbatim}
\end{center}

	Para que os testes no algoritmo tenham uma cobertura mais ampla, criamos dados de entrada que executam todas as operações e permeiam por todos os fluxos do programa. Além disso, é possível criar dados de entrada aleatórios dado um comprimento de genoma desejado a partir do programa.
	
\section{Estrutura de Dados}

As estruturas de dados usadas foram simplesmente matrizes e vetores. O algoritmo utiliza duas matrizes para cada genoma, duas matrizes de adjacências, $genome1\_adjacency$ e
 $genome2\_adjacency$, que organizam as cabeças e caudas dos genes dependendo da orientação dos mesmos e é indexada pela posição da adjacência no genoma, e uma matriz de
 localização, $genome1\_location$ e $genome2\_location$, que é indexada pelos genes e consiste na posição na qual o gene se localiza na matriz de adjacências.
	
Foram usadas outras estruturas auxiliares para identificar em qual componente um certo gene se encontra e para identificar o tipo de componente.
 A estrutura para identificar em qual componente um certo gene se encontra é um vetor que contém o índice do componente, e como possui o mesmo tamanho e
 índices da $genome1\_location$, optamos por armazená-lo como uma linha dessa matriz.
 A estrutura para identificar o tipo de componente, se é um componente linear um ou ciclo, é um vetor indexado pelo índice do componente e contém uma flag $COMP\_LINEAR$
 (para componentes linear) ou $COMP\_CYCLE$ (para ciclos). Tais estruturas se demonstraram necessárias para a identificação de operações, e introduzem mais passos no algoritmo
 mas sem prejudicar sua complexidade total, e só se aplicam ao genoma de origem.

\section{Identificação de Operações}

Para identificar as operações, é necessário inspecionar em quais componentes e quais os tipos de componentes dos genes afetados pela operação da iteração.
 Essa inspeção exige mais duas estruturas de dados (descritas anteriormente) que são atualizadas a cada iteração.

\section{Modelo Restrito}

O modelo restrito foi implementado como um fluxo adicional, que é usado quando é passada uma opção na chamada do programa. Quando esse fluxo é ativado,
 a cada iteração nas adjacências, é verificada a existência de ciclos, e é executada mais uma operação para desfazê-los.

%\section{Modificações do Algoritmo para a Implementação}

\begin{thebibliography}{9}

\bibitem{Bergeron}
 Anne Bergeron, Julia Mixtacki e Jens Stoye\\
 A unifying view of genome rearrangements

\bibitem{Kovac}
 Jakub Kovac, Robert Warren, Marlia D. V. Braga e Jens Stoye\\
 Restricted DCJ Model (The Problem of Chromosome Reincorporation)

\end{thebibliography}

\end{document}
